package com.hjx.leetcode;

/**
 * 链接：https://leetcode-cn.com/problems/sort-list/comments/
 * 1、思路 nlogn  快排  归并排序
 * 2、归并排序  先找中点， 然后不断拆分 直到一个或0个节点 然后比较后合并  再不断合并
 */
class LeetCode_148 {

    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }


    private ListNode mergeSort(ListNode head) {
        //1、 如果没有节点 或只有一个 节点直接返回
        if (head == null || head.next == null) { return head; }

        //2、快慢指针找中间节点
        ListNode slowP = head, fastP = head.next.next;
        //TODO:易错部分：快指针 指向的节点和其下一个节点都不为null (快慢指针法的理解不到位)
        while(fastP != null && fastP.next != null) {
            // 走一步
            slowP = slowP.next;
            // 走两步
            fastP = fastP.next.next;
        }

        //3、右半部分排序
        ListNode r = mergeSort(slowP.next);

        //TODO：关键点 左右链表断开的方法 找到中间节点 链表一分为二  head 到p部分  p到末尾
        slowP.next = null;

        //4、左半部分排序
        ListNode l = mergeSort(head);

        //5、比较大小并合并
        return merge(l, r);
    }

    /**
     * 从头到尾按顺序遍历左右两个链接 val小的在前, 然后移动指针
     * @param l
     * @param r
     * @return
     */
    private ListNode merge(ListNode l, ListNode r) {
        // 这个头节点 主要为了便于处理
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        //左右两个链表都不为空
        while (l != null && r != null) {
            // 左链表 值小于右链表的值
            if (l.val < r.val) {
                cur.next = l;
                // cur 向后移动
                cur = cur.next;
                //TODO：这一步也很关键 l 向后移动 不这么做无法比较后续节点
                l = l.next;
            } else {
                cur.next = r;
                cur = cur.next;
                r = r.next;
            }
        }
        //左右有一个为null 那cur直接指向非空链表
        if (l == null) {
            cur.next = r;
        }
        if (r == null) {
            cur.next = l;
        }

        //返回dummy后续节点
        return dummy.next;
    }

}
